package LeetCode刷题;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-12-31 11:05
 * @description: Functions of this class is
 * 民间牛人题解：
 * public int canCompleteCircuit(int[] gas, int[] cost) {
 *     int len = gas.length;
 *     int spare = 0;
 *     int minSpare = Integer.MAX_VALUE;
 *     int minIndex = 0;
 *     for (int i = 0; i < len; i++) {
 *         spare += gas[i] - cost[i];//遍历全部点，汇总其总油量，
 *         if (spare < minSpare) {//遍历过程中找到最低点
 *             minSpare = spare;
 *             minIndex = i;
 *         }
 *     }
 *     //最后判断总油量是否>=0，是的话就直接返回最低点前面那一个位置（因为总油量是>=0的了，所以最低点之后开始，其点就会越来越高，也就说明
 *     return spare < 0 ? -1 : (minIndex + 1) % len;
 * }
 **/
public class NoNo加油站 {
    //直接暴力的普通方法，超时了！超时了！超时了！超时了！
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int len=gas.length;
        for(int i=0;i<len;i++){
            //枚举每一个加油站，从这些加油站开始走，看能否走回来
            int beginIndex=i;
            if(gas[beginIndex]>=cost[beginIndex]){//只有当起点的加油量足够汽车开往下一个地点的时候,才能往后开
                int sum=gas[beginIndex];
                while(sum-cost[beginIndex]>=0){
                    sum-=cost[beginIndex];
                    ++beginIndex;//向前走
                    if(beginIndex==len){
                        beginIndex=0;//从头开始;
                    }
                    if(sum>=0&&beginIndex==i){
                        return beginIndex;
                    }
                    sum+=gas[beginIndex];
                }
            }
        }
        return -1;
    }

}